package sort;

import java.util.Arrays;

public class HeapSort {
    //堆排序
    public static void main(String[] args) {
        int[] arr = {18,25,2,82,1,38,96,69};
        heapSort(arr);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.print(arr[i] + " ");
//        }
//        System.out.println();
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr){
        //堆排序
        //1.创建大根堆
        createBigHeap(arr);
        for (int end = arr.length - 1; end > 0; end--) {
            //2.交换堆首元素和堆尾元素
            swap(arr,0,end);
            //3.除最后一个元素，其余元素建立大根堆
            shiftDown(arr,0,end);
        }


    }
    //创建大根堆
    public static void createBigHeap(int[] arr){
        for(int i = (arr.length-1-1)/2;i >= 0;i--){
            //向下调整实现大根堆
            shiftDown(arr,i,arr.length);
        }
    }
    public static void shiftDown(int[] arr,int parent,int len){
        int child = 2 * parent + 1;
        while(child < len){
            //右孩子存在
            if(child + 1 < len && arr[child] < arr[child + 1]){
                child = child + 1;
            }
            //右孩子不存在
            if (arr[child] > arr[parent]){
                swap(arr,child,parent);
            }else{
                break;
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }
    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
